#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, k;

void solve(const vector<vector<vector<int> > >& graph)
{
	vector<int> prev(n, INT_MAX);
	prev[0] = 0;
	
	for(int i=0; i<k; i++)
	{
		vector<int>next(n, INT_MAX);
		for(int j=0; j<n; j++)
		{
			if(prev[j] == INT_MAX)
				continue;
				
			for(int k=0; k<n; k++)
			{
				const vector<int>&v = graph[j][k];
				int cost = v[i % (int)v.size()];
				if(cost == 0)
					continue;
				next[k] = min(next[k], prev[j] + cost);
			}
		}
		swap(prev, next);
	}
	
	if (prev[n - 1] != INT_MAX)
		cout << "The best flight costs " << prev[n - 1] << "." << endl << endl;
	else 
		cout << "No flight possible." << endl;
}

void read()
{
	int counter = 0;
	while(cin >> n >> k && n && k)
	{
		int d;
		int cost;
		vector<vector<int> > init(n);
		vector<vector<vector<int> > > graph(n, init);
		//Graph Construction
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
			{
				//Get the vector of i = from and j = to
				vector<int>&v = graph[i][j];
				if(i == j)
				{
					v.push_back(0);
					continue;
				}
				cin >> d;
				for(int k=0; k<d; k++)
				{
					cin >> cost;
					v.push_back(cost);
				}
			}
		
		cout << "Scenario #" << ++counter << endl;
		solve(graph);
	}
}

int main()
{
	read();
	return 0;
}
